#include "mgraph.h"
#include <memory.h>
#include <list>

using std::cout;
using std::endl;
using std::list;

MGraph::MGraph()
{
	memset(this->vexs, 0, sizeof(this->vexs));
	memset(this->visited, 0, sizeof(this->visited));
	memset(this->arcs, 0, sizeof(this->arcs));
	this->vexnum = this->arcnum = 0;
}

Status MGraph::CreateGraph()
{
	return OK;
}

Status MGraph::DestroyGraph()
{
	memset(this->vexs, 0, sizeof(this->vexs));
	memset(this->visited, 0, sizeof(this->visited));
	memset(this->arcs, 0, sizeof(this->arcs));
	this->vexnum = this->arcnum = 0;
	return OK;
}

int MGraph::LocateVex(VertexType *u)
{
	if(u-(this->vexs) >= 0 && u-(this->vexs) < this->vexnum)
		return u-this->vexs;					//返回该顶点编号
	return -1;							//没有找到该顶点
}

VertexType MGraph::GetVex(VertexType v)
{
	int i;
	for(i = 0; i < this->vexnum; i++)
		if(this->vexs[i] == v)
			return v;
	cout << "The vertex is not exist" << endl;
	return ERROR;
}

VertexType *MGraph::GetVexAddress(VertexType v)
{
	int i;
	for(i = 0; i < this->vexnum; i++)
		if(this->vexs[i] == v)
			return this->vexs+v;
	cout << "The vertex is not exist" << endl;
	return NULL;
}

Status MGraph::Putvex(VertexType *v, VertexType value)
{
	if(v-(this->vexs) >= 0 && v-(this->vexs) < this->vexnum)
	{
		*v = value;
		return OK;
	}
	else
		return ERROR;
}

VertexType *MGraph::FirstAdjVex(VertexType *v)
{
	int startvex; 
	if(v-(this->vexs) >= 0 && v-(this->vexs) < this->vexnum)
	{
		startvex = v-(this->vexs);
		for(int i = 0; i < this->vexnum; i++)
			if(this->arcs[startvex][i].adj)
				return vexs+i;
		cout << "The adjacent vertex is not exist" << endl;
		return NULL;
	}
	else 
	{
		cout << "The vertex is not exist" << endl;
		return NULL;
	}
}

VertexType *MGraph::NextAdjVex(VertexType *v, VertexType *w)
{
	int startvex, adjvex;
	startvex = v-(this->vexs);
	adjvex = w-(this->vexs);
	if((startvex >= 0 && startvex < this->vexnum) || (adjvex >= 0 && adjvex < this->vexnum))
	{
		cout << "The vertex is not exist" << endl;
		return NULL;
	}
	for(int i = adjvex+1; i < this->vexnum; i++)
		if(this->arcs[startvex][i].adj)
			return vexs+i;
	cout << "The adjacent vertex is not exist" << endl;
	return NULL;
}

Status MGraph::InsertVex(VertexType *v)
{
	if(this->vexnum == MAX_VERTEX_NUM)
		return OVERFLOW;
	this->vexnum++;
	this->vexs[vexnum] = *v;
	return OK;
}

Status MGraph::DeleteVex(VertexType *v)
{
	int vexp;
	int i, j;
	if(v-(this->vexs) >= 0 && v-(this->vexs) < this->vexnum)
		return ERROR;
	vexp = v-(this->vexs);
	for(i = vexp+1; i < this->vexnum; i++)
		this->vexs[i-1] = this->vexs[i];
	for(i = vexp+1; i < this->vexnum; i++)
		for(j = 0; j < this->vexnum; j++)
			this->arcs[i-1][j] = this->arcs[i][j];
	for(i = vexp+1; i < this->vexnum; i++)
		for(j = 0; j < this->vexnum; j++)
				this->arcs[j][i-1] = this->arcs[j][i];
	for(i = 0; i < this->vexnum; i++)
	{
		this->arcs[this->vexnum-1][i].adj = 0;
		this->arcs[i][this->vexnum-1].adj = 0;
	}
	this->vexnum--;
	return OK;
}

Status MGraph::InsertArc(VertexType *v, VertexType *w)
{
	int vexa = v-this->vexs, vexb = w-this->vexs;
	if(vexa >= 0 && vexa < this->vexnum)
		return ERROR;
	if(vexb >= 0 && vexb < this->vexnum)
		return ERROR;
	this->arcs[vexa][vexb].adj = 1;
	return OK;
}

Status MGraph::DeleteArc(VertexType *v, VertexType *w)
{
	int vexa = v-this->vexs, vexb = w-this->vexs;
	if(vexa >= 0 && vexa < this->vexnum)
		return ERROR;
	if(vexb >= 0 && vexb < this->vexnum)
		return ERROR;
	this->arcs[vexa][vexb].adj = 0;
	return OK;
}

Status MGraph::DFSTraverse(Status (*visit)(VertexType v), int v = 0)
{
	memset(this->visited, 0, sizeof(this->visited));
	this->visited[v] = true;
	(*visit)(this->vexs[v]);
	for(int i = 1; i < this->vexnum; i++)
		if(this->arcs[v][i].adj && (!this->visited[i]))
			this->DFSTraverse(visit, i);
	return OK;
}

Status MGraph::BFSTraverse(Status (*visit)(VertexType v))
{
	memset(this->visited, 0, sizeof(this->visited));
	list<int> queue;
	int cur;
	queue.push_back(0);
	while(!queue.empty())
	{
		cur = queue.front();
		queue.pop_front();
		if(!this->visited[cur])
			(*visit)(this->vexs[cur]);
		for(int i = 0; i < this->vexnum; i++)
			if(this->arcs[cur][i].adj && (!this->visited[cur]))
				queue.push_back(i);
	}
	return OK;
}
